#define _CRT_SECURE_NO_WARNINGS 1

class LRUCache
{
    using LRUIterator = list<pair<int, int>>::iterator;
    int _capacity;
    unordered_map<int, LRUIterator> _hash;
    list<pair<int, int>> _LRUList;
public:
    LRUCache(int capacity)
        :_capacity(capacity)
    {
    }

    int get(int key)
    {
        auto ret = _hash.find(key);
        if (ret != _hash.end())
        {
            LRUIterator it = ret->second;
            _LRUList.splice(_LRUList.begin(), _LRUList, it);
            return it->second;
        }
        return -1;

    }

    void put(int key, int value)
    {
        auto ret = _hash.find(key);
        if (ret != _hash.end())
        {
            LRUIterator it = ret->second;
            it->second = value;
            _LRUList.splice(_LRUList.begin(), _LRUList, it);
        }
        else
        {
            if (_hash.size() == _capacity)
            {
                auto it = _LRUList.back();
                _hash.erase(it.first);
                _LRUList.pop_back();
            }
            _LRUList.push_front({ key, value });
            _hash[key] = _LRUList.begin();
        }

    }
};

class Solution
{
    struct cmp
    {
        bool operator()(ListNode* p1, ListNode* p2)
        {
            return p1->val > p2->val;
        }
    };
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;

        for (auto e : lists)
        {
            if (e != nullptr) pq.push(e);
        }

        ListNode* newhead = new ListNode;
        ListNode* newtail = newhead;
        while (pq.size())
        {
            ListNode* top = pq.top();
            pq.pop();
            if (top->next) pq.push(top->next);
            newtail->next = top;
            newtail = newtail->next;
        }
        ListNode* ret = newhead->next;
        delete newhead;

        return ret;
    }
};
class Solution {
public:
    ListNode* sortList(ListNode* head)
    {
        if (!head || !head->next) return head;
        ListNode* slow = head, * fast = head->next;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* cur2 = slow->next;
        slow->next = nullptr;
        ListNode* cur1 = head;

        ListNode* p1 = sortList(cur1);
        ListNode* p2 = sortList(cur2);

        ListNode* newhead = new ListNode;
        ListNode* newtail = newhead;

        while (p1 && p2)
        {
            if (p1->val < p2->val)
            {
                newtail->next = p1;
                p1 = p1->next;
            }
            else
            {
                newtail->next = p2;
                p2 = p2->next;
            }
            newtail = newtail->next;
        }

        if (p1) newtail->next = p1;
        else newtail->next = p2;

        ListNode* ret = newhead->next;
        delete newhead;

        return ret;
    }
};
class Solution {
public:
    Node* copyRandomList(Node* head)
    {
        Node* newhead = new Node(0);
        Node* cur = head;
        Node* prev = newhead;

        unordered_map<Node*, Node*> hash;
        while (cur)
        {
            Node* newnode = new Node(cur->val);
            prev->next = newnode;
            hash[cur] = newnode;
            prev = prev->next;

            cur = cur->next;
        }

        cur = head;
        while (cur)
        {
            hash[cur]->random = hash[cur->random];
            cur = cur->next;
        }

        Node* ret = newhead->next;
        delete newhead;
        return ret;
    }
};
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k)
    {
        int count = 0;
        ListNode* cur = head;
        while (cur)
        {
            count++;
            cur = cur->next;
        }

        int n = count / k;
        ListNode* newhead = new ListNode;
        ListNode* prev = newhead;
        cur = head;
        ListNode* next = cur->next;
        while (n--)
        {
            ListNode* tmp = nullptr;
            for (int i = 0; i < k; i++)
            {
                if (i == 0)
                {
                    tmp = cur;
                }
                cur->next = prev->next;
                prev->next = cur;
                cur = next;
                if (cur) next = cur->next;
            }
            prev = tmp;
        }
        prev->next = cur;
        ListNode* ret = newhead->next;
        delete newhead;

        return ret;
    }
};
class Solution {
public:
    ListNode* swapPairs(ListNode* head)
    {
        if (!head || !head->next) return head;

        ListNode* cur = head, * next = head->next, * p = head->next->next;
        next->next = cur;
        cur->next = swapPairs(p);

        return next;
    }
};
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n)
    {
        ListNode* p1 = head, * p2 = head;
        ListNode* prev = nullptr;

        while (n--) p2 = p2->next;

        if (p2 == nullptr)
        {
            ListNode* ret = p1->next;
            delete p1;
            return ret;
        }

        while (p2)
        {
            prev = p1;
            p1 = p1->next;
            p2 = p2->next;
        }

        prev->next = p1->next;
        delete p1;

        return head;
    }
};
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n)
    {
        ListNode* p1 = head, * p2 = head;
        ListNode* prev = nullptr;

        while (n--) p2 = p2->next;

        if (p2 == nullptr)
        {
            ListNode* ret = p1->next;
            delete p1;
            return ret;
        }

        while (p2)
        {
            prev = p1;
            p1 = p1->next;
            p2 = p2->next;
        }

        prev->next = p1->next;
        delete p1;

        return head;
    }
};
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
    {
        ListNode* p1 = l1, * p2 = l2;
        int add = 0;

        ListNode* newhead = new ListNode;
        ListNode* newtail = newhead;

        while (p1 || p2 || add)
        {
            if (p1)
            {
                add += p1->val;
                p1 = p1->next;
            }
            if (p2)
            {
                add += p2->val;
                p2 = p2->next;
            }
            ListNode* newnode = new ListNode(add % 10);
            add /= 10;
            newnode->next = newtail->next;
            newtail->next = newnode;
            newtail = newtail->next;
        }

        ListNode* ret = newhead->next;
        delete newhead;

        return ret;
    }
};






